﻿// By Huang Yuanbing 2019-2022
// bailuzhou@163.com
// version 2.1.0

// LICENSE:
//   This software is dual-licensed to the public domain and under the following
//   license: you are granted a perpetual, irrevocable license to copy, modify,
//   publish, and distribute this file as you see fit.

// From
// NUMBER OF PROBES / LOOKUP       Successful            Unsuccessful
// Quadratic collision resolution   1 - ln(1-L) - L/2    1/(1-L) - L - ln(1-L)
// Linear collision resolution     [1+1/(1-L)]/2         [1+1/(1-L)2]/2
//
// -- enlarge_factor --           0.10  0.50  0.60  0.75  0.80  0.90  0.99
// QUADRATIC COLLISION RES.
//    probes/successful lookup    1.05  1.44  1.62  2.01  2.21  2.85  5.11
//    probes/unsuccessful lookup  1.11  2.19  2.82  4.64  5.81  11.4  103.6
// LINEAR COLLISION RES.
//    probes/successful lookup    1.06  1.5   1.75  2.5   3.0   5.5   50.5
//    probes/unsuccessful lookup  1.12  2.5   3.6   8.5   13.0  50.0

#pragma once

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iterator>
#include <type_traits>
#include <utility>

#ifdef __has_include
#if __has_include("wyhash.h")
#include "wyhash.h"
#endif
#elif EMHASH_WY_HASH
#include "wyhash.h"
#endif

#ifdef EMH_KEY
#undef EMH_KEY
#undef EMH_VAL
#undef NEXT_BUCKET
#undef EMH_PKV
#undef NEW_KVALUE
#endif

// likely/unlikely
#if (__GNUC__ >= 4 || __clang__)
#define EMHASH_LIKELY(condition) __builtin_expect(condition, 1)
#define EMHASH_UNLIKELY(condition) __builtin_expect(condition, 0)
#else
#define EMHASH_LIKELY(condition) condition
#define EMHASH_UNLIKELY(condition) condition
#endif

#define EMH_KEY(p, n) p[n].first
#define EMH_VAL(p, n) p[n].second
#define NEXT_BUCKET(p, n) p[n].bucket
#define EMH_PKV(p, n) p[n]
#define NEW_KVALUE(key, value, bucket)             \
  new (_pairs + bucket) PairT(key, value, bucket); \
  _num_filled++;                                   \
  update_orderid(_pairs[bucket].orderid)

namespace emlru_size {

    constexpr uint32_t INACTIVE = 0xFFFFFFFF;

    inline static constexpr uint32_t incid() {
#if EMHASH_LRU_TIME > 0
        return EMHASH_LRU_TIME;
#else
        return 1;
#endif
    }

    template <typename First, typename Second>
    struct entry {
        inline static uint32_t nextid() {
#if EMHASH_SET_TIME
            return EMHASH_SET_TIME;
#elif EMHASH_LRU_TIME
            return time(0);
#else
            static uint32_t _sid = 0;
            return ++_sid;  // overflow
#endif
        }

        entry(const First& key, const Second& value, uint32_t ibucket)
            : second(value), first(key) {
            bucket = ibucket;
            orderid = nextid();
        }

        entry(First&& key, Second&& value, uint32_t ibucket)
            : second(std::move(value)), first(std::move(key)) {
            bucket = ibucket;
            orderid = nextid();
        }

        template <typename K, typename V>
        entry(K&& key, V&& value, uint32_t ibucket)
            : second(std::forward<V>(value)), first(std::forward<K>(key)) {
            bucket = ibucket;
            orderid = nextid();
        }

        entry(const std::pair<First, Second>& pair)
            : second(pair.second), first(pair.first) {
            bucket = INACTIVE;
            orderid = nextid();
        }

        entry(std::pair<First, Second>&& pair)
            : second(std::move(pair.second)), first(std::move(pair.first)) {
            bucket = INACTIVE;
            orderid = nextid();
        }

        entry(const entry& pairT) : second(pairT.second), first(pairT.first) {
            bucket = pairT.bucket;
            orderid = pairT.orderid;
        }

        entry(entry&& pairT)
            : second(std::move(pairT.second)), first(std::move(pairT.first)) {
            bucket = pairT.bucket;
            orderid = pairT.orderid;
        }

        entry& operator=(entry&& pairT) {
            second = std::move(pairT.second);
            first = std::move(pairT.first);
            bucket = pairT.bucket;
            orderid = pairT.orderid;
            return *this;
        }

        entry& operator=(entry& o) {
            second = o.second;
            first = o.first;
            bucket = o.bucket;
            orderid = o.orderid;
            return *this;
        }

        void swap(entry<First, Second>& o) {
            std::swap(second, o.second);
            std::swap(first, o.first);
            std::swap(orderid, o.orderid);
        }

        Second second;  // int
        First first;    // long
        uint32_t bucket;
        uint32_t orderid;
    };  // __attribute__ ((packed));

    /// A cache-friendly hash table with open addressing, linear/qua probing and
    /// power-of-two capacity
    template <typename KeyT,
        typename ValueT,
        typename HashT = std::hash<KeyT>,
        typename EqT = std::equal_to<KeyT>>
        class lru_cache {
        private:
            typedef lru_cache<KeyT, ValueT, HashT, EqT> htype;
            typedef entry<KeyT, ValueT> PairT;
            typedef entry<KeyT, ValueT> value_pair;

        public:
            typedef KeyT key_type;
            typedef ValueT mapped_type;

            typedef size_t size_type;
            typedef std::pair<KeyT, ValueT> value_type;
            typedef PairT& reference;
            typedef const PairT& const_reference;

            class iterator {
            public:
                typedef std::forward_iterator_tag iterator_category;
                typedef std::ptrdiff_t difference_type;
                typedef value_pair value_type;

                typedef value_pair* pointer;
                typedef value_pair& reference;

                iterator() {}
                iterator(htype* hash_map, uint32_t bucket)
                    : _map(hash_map), _bucket(bucket) {
                }

                iterator& operator++() {
                    goto_next_element();
                    return *this;
                }

                iterator operator++(int) {
                    auto old_index = _bucket;
                    goto_next_element();
                    return { _map, old_index };
                }

                reference operator*() const { return _map->EMH_PKV(_pairs, _bucket); }

                pointer operator->() const { return &(_map->EMH_PKV(_pairs, _bucket)); }

                bool operator==(const iterator& rhs) const {
                    return _bucket == rhs._bucket;
                }

                bool operator!=(const iterator& rhs) const {
                    return _bucket != rhs._bucket;
                }

            private:
                void goto_next_element() {
                    do {
                        _bucket++;
                    } while (_map->NEXT_BUCKET(_pairs, _bucket) == INACTIVE);
                }

            public:
                htype* _map;
                uint32_t _bucket;
            };

            class const_iterator {
            public:
                typedef std::forward_iterator_tag iterator_category;
                typedef std::ptrdiff_t difference_type;
                typedef value_pair value_type;

                typedef value_pair* pointer;
                typedef value_pair& reference;

                const_iterator() {}
                const_iterator(const iterator& proto)
                    : _map(proto._map), _bucket(proto._bucket) {
                }
                const_iterator(const htype* hash_map, uint32_t bucket)
                    : _map(hash_map), _bucket(bucket) {
                }

                const_iterator& operator++() {
                    goto_next_element();
                    return *this;
                }

                const_iterator operator++(int) {
                    auto old_index = _bucket;
                    goto_next_element();
                    return { _map, old_index };
                }

                reference operator*() const { return _map->EMH_PKV(_pairs, _bucket); }

                pointer operator->() const { return &(_map->EMH_PKV(_pairs, _bucket)); }

                bool operator==(const const_iterator& rhs) const {
                    return _bucket == rhs._bucket;
                }

                bool operator!=(const const_iterator& rhs) const {
                    return _bucket != rhs._bucket;
                }

            private:
                void goto_next_element() {
                    do {
                        _bucket++;
                    } while (_map->NEXT_BUCKET(_pairs, _bucket) == INACTIVE);
                }

            public:
                const htype* _map;
                uint32_t _bucket;
            };

            // ------------------------------------------------------------------------

            void init(uint32_t max_bucket = 1 << 10) {
                _num_buckets = 0;
                _mask = 0;
                _sum_orderid = 0;
                _pairs = nullptr;
                _num_filled = 0;
                _max_buckets = max_bucket;
                max_load_factor(0.85f);
            }

            lru_cache(uint32_t bucket = 8, uint32_t max_bucket = 1 << 28) {
                init(max_bucket);
                reserve(bucket);
            }

            lru_cache(const lru_cache& other) {
                _pairs = (PairT*)malloc((2 + other._num_buckets) * sizeof(PairT));
                clone(other);
            }

            lru_cache(lru_cache&& other) {
                init(other._max_bucket);
                reserve(1);
                *this = std::move(other);
            }

            /**
            lru_cache(std::initializer_list<std::pair<KeyT, ValueT>> il)
            {
                init(il.size() * 2);
                reserve((uint32_t)il.size());
                for (auto begin = il.begin(); begin != il.end(); ++begin)
                    insert(*begin);
            }*/

            lru_cache& operator=(const lru_cache& other) {
                if (this == &other)
                    return *this;

                if (is_notrivially())
                    clearkv();

                if (_num_buckets != other._num_buckets) {
                    free(_pairs);
                    _pairs = (PairT*)malloc((2 + other._num_buckets) * sizeof(PairT));
                }

                clone(other);
                return *this;
            }

            lru_cache& operator=(lru_cache&& other) {
                if (this != &other) {
                    swap(other);
                    other.clear();
                }
                return *this;
            }

            ~lru_cache() {
                if (is_notrivially())
                    clearkv();

                free(_pairs);
            }

            void clone(const lru_cache& other) {
                _hasher = other._hasher;
                _num_buckets = other._num_buckets;
                _num_filled = other._num_filled;
                _mask = other._mask;
                _loadlf = other._loadlf;
                _max_buckets = other._max_buckets;
                _sum_orderid = other._sum_orderid;
                auto opairs = other._pairs;

                if (std::is_pod<KeyT>::value && std::is_pod<ValueT>::value) {
                    memcpy(_pairs, opairs, (_num_buckets + 2) * sizeof(PairT));
                }
                else {
                    for (uint32_t bucket = 0; bucket < _num_buckets; bucket++) {
                        auto next_bucket = NEXT_BUCKET(_pairs, bucket) =
                            NEXT_BUCKET(opairs, bucket);
                        if (next_bucket != INACTIVE)
                            new (_pairs + bucket) PairT(opairs[bucket]);
                    }
                    NEXT_BUCKET(_pairs, _num_buckets) =
                        NEXT_BUCKET(_pairs, _num_buckets + 1) = 0;
                }
            }

            void swap(lru_cache& other) {
                std::swap(_hasher, other._hasher);
                std::swap(_pairs, other._pairs);
                std::swap(_num_buckets, other._num_buckets);
                std::swap(_num_filled, other._num_filled);
                std::swap(_mask, other._mask);
                std::swap(_loadlf, other._loadlf);
                std::swap(_max_buckets, other._max_buckets);
                std::swap(_sum_orderid, other._sum_orderid);
            }

            // -------------------------------------------------------------
            iterator begin() {
                uint32_t bucket = 0;
                while (NEXT_BUCKET(_pairs, bucket) == INACTIVE) {
                    ++bucket;
                }
                return { this, bucket };
            }

            const_iterator cbegin() const {
                uint32_t bucket = 0;
                while (NEXT_BUCKET(_pairs, bucket) == INACTIVE) {
                    ++bucket;
                }
                return { this, bucket };
            }

            const_iterator begin() const { return cbegin(); }

            iterator end() { return { this, _num_buckets }; }

            const_iterator cend() const { return { this, _num_buckets }; }

            const_iterator end() const { return { this, _num_buckets }; }

            size_type size() const { return _num_filled; }

            bool empty() const { return _num_filled == 0; }

            // Returns the number of buckets.
            size_type bucket_count() const { return _num_buckets; }

            /// Returns average number of elements per bucket.
            float load_factor() const {
                return static_cast<float>(_num_filled) / (_mask + 1);
            }

            HashT& hash_function() const { return _hasher; }

            EqT& key_eq() const { return _eq; }

            constexpr float max_load_factor() const { return (1 << 27) / (float)_loadlf; }

            void max_load_factor(float value) {
                if (value < 0.95f && value > 0.2f)
                    _loadlf = (uint32_t)((1 << 27) / value);
            }

            constexpr size_type max_size() const { return (1 << 30); }

            constexpr size_type max_bucket_count() const { return (1 << 30); }

#ifdef EMHASH_STATIS
            // Returns the bucket number where the element with key k is located.
            size_type bucket(const KeyT& key) const {
                const auto bucket = hash_bucket(key);
                const auto next_bucket = NEXT_BUCKET(_pairs, bucket);
                if (next_bucket == INACTIVE)
                    return 0;
                else if (bucket == next_bucket)
                    return bucket + 1;

                const auto& bucket_key = EMH_KEY(_pairs, bucket);
                return hash_bucket(bucket_key) + 1;
            }

            // Returns the number of elements in bucket n.
            size_type bucket_size(const uint32_t bucket) const {
                auto next_bucket = NEXT_BUCKET(_pairs, bucket);
                if (next_bucket == INACTIVE)
                    return 0;

                const auto& bucket_key = EMH_KEY(_pairs, bucket);
                next_bucket = hash_bucket(bucket_key);
                uint32_t ibucket_size = 1;

                // iterator each item in current main bucket
                while (true) {
                    const auto nbucket = NEXT_BUCKET(_pairs, next_bucket);
                    if (nbucket == next_bucket) {
                        break;
                    }
                    ibucket_size++;
                    next_bucket = nbucket;
                }
                return ibucket_size;
            }

            size_type get_main_bucket(const uint32_t bucket) const {
                auto next_bucket = NEXT_BUCKET(_pairs, bucket);
                if (next_bucket == INACTIVE)
                    return INACTIVE;

                const auto& bucket_key = EMH_KEY(_pairs, bucket);
                const auto main_bucket = hash_bucket(bucket_key);
                return main_bucket;
            }

            size_type get_cache_info(uint32_t bucket, uint32_t next_bucket) const {
                auto pbucket = reinterpret_cast<std::uintptr_t>(&_pairs[bucket]);
                auto pnext = reinterpret_cast<std::uintptr_t>(&_pairs[next_bucket]);
                if (pbucket / 64 == pnext / 64)
                    return 0;
                auto diff = pbucket > pnext ? (pbucket - pnext) : pnext - pbucket;
                if (diff < 127 * 64)
                    return diff / 64 + 1;
                return 127;
            }

            int get_bucket_info(const uint32_t bucket,
                uint32_t steps[],
                const uint32_t slots) const {
                auto next_bucket = NEXT_BUCKET(_pairs, bucket);
                if (next_bucket == INACTIVE)
                    return -1;

                const auto& bucket_key = EMH_KEY(_pairs, bucket);
                const auto main_bucket = hash_bucket(bucket_key);
                if (main_bucket != bucket)
                    return 0;
                else if (next_bucket == bucket)
                    return 1;

                steps[get_cache_info(bucket, next_bucket) % slots]++;
                uint32_t ibucket_size = 2;
                // find a new empty and linked it to tail
                while (true) {
                    const auto nbucket = NEXT_BUCKET(_pairs, next_bucket);
                    if (nbucket == next_bucket)
                        break;

                    steps[get_cache_info(nbucket, next_bucket) % slots]++;
                    ibucket_size++;
                    next_bucket = nbucket;
                }
                return ibucket_size;
            }

            void dump_statis() const {
                uint32_t buckets[129] = { 0 };
                uint32_t steps[129] = { 0 };
                for (uint32_t bucket = 0; bucket < _num_buckets; ++bucket) {
                    auto bsize = get_bucket_info(bucket, steps, 128);
                    if (bsize > 0)
                        buckets[bsize]++;
                }

                uint32_t sumb = 0, collision = 0, sumc = 0, finds = 0, sumn = 0;
                puts("============== buckets size ration =========");
                for (uint32_t i = 0; i < sizeof(buckets) / sizeof(buckets[0]); i++) {
                    const auto bucketsi = buckets[i];
                    if (bucketsi == 0)
                        continue;
                    sumb += bucketsi;
                    sumn += bucketsi * i;
                    collision += bucketsi * (i - 1);
                    finds += bucketsi * i * (i + 1) / 2;
                    printf("  %2u  %8u  %.2lf  %.2lf\n", i, bucketsi,
                        bucketsi * 100.0 * i / _num_filled, sumn * 100.0 / _num_filled);
                }

                puts("========== collision miss ration ===========");
                for (uint32_t i = 0; i < sizeof(steps) / sizeof(steps[0]); i++) {
                    sumc += steps[i];
                    if (steps[i] <= 2)
                        continue;
                    printf("  %2u  %8u  %.2lf  %.2lf\n", i, steps[i],
                        steps[i] * 100.0 / collision, sumc * 100.0 / collision);
                }

                if (sumb == 0)
                    return;
                printf(
                    "    _num_filled/bucket_size/packed collision/cache_miss/hit_find = "
                    "%u/%.2lf/%zd/ %.2lf%%/%.2lf%%/%.2lf\n",
                    _num_filled, _num_filled * 1.0 / sumb, sizeof(PairT),
                    (collision * 100.0 / _num_filled),
                    (collision - steps[0]) * 100.0 / _num_filled,
                    finds * 1.0 / _num_filled);
                assert(sumn == _num_filled);
                assert(sumc == collision);
            }
#endif

            // ------------------------------------------------------------

            iterator find(const KeyT& key) noexcept {
                return { this, find_filled_bucket(key) };
            }

            const_iterator find(const KeyT& key) const noexcept {
                return { this, find_filled_bucket(key) };
            }

            bool contains(const KeyT& key) const noexcept {
                return find_filled_bucket(key) != _num_buckets;
            }

            size_type count(const KeyT& key) const noexcept {
                return find_filled_bucket(key) == _num_buckets ? 0 : 1;
            }

            std::pair<iterator, iterator> equal_range(const KeyT& key) {
                const auto found = find(key);
                if (found == end())
                    return { found, found };
                else
                    return { found, std::next(found) };
            }

            /// Returns false if key isn't found.
            bool try_get(const KeyT& key, ValueT& val) const noexcept {
                const auto bucket = find_filled_bucket(key);
                const auto found = bucket != _num_buckets;
                if (found) {
                    val = EMH_VAL(_pairs, bucket);
                }
                return found;
            }

            /// Returns the matching ValueT or nullptr if k isn't found.
            ValueT* try_get(const KeyT& key) noexcept {
                const auto bucket = find_filled_bucket(key);
                return bucket == _num_buckets ? nullptr : &EMH_VAL(_pairs, bucket);
            }

            /// Const version of the above
            ValueT* try_get(const KeyT& key) const noexcept {
                const auto bucket = find_filled_bucket(key);
                return bucket == _num_buckets ? nullptr : &EMH_VAL(_pairs, bucket);
            }

            /// Convenience function.
            ValueT get_or_return_default(const KeyT& key) const noexcept {
                const auto bucket = find_filled_bucket(key);
                return bucket == _num_buckets ? ValueT() : EMH_VAL(_pairs, bucket);
            }

            // -----------------------------------------------------

            /// Returns a pair consisting of an iterator to the inserted element
            /// (or to the element that prevented the insertion)
            /// and a bool denoting whether the insertion took place.
            std::pair<iterator, bool> insert(const KeyT& key, const ValueT& value) {
                check_expand_need();
                const auto bucket = find_or_allocate(key);
                const auto found = NEXT_BUCKET(_pairs, bucket) == INACTIVE;
                if (found) {
                    NEW_KVALUE(key, value, bucket);
                }
                else {
                    _pairs[bucket].orderid += incid();
                    update_orderid(incid());
                }
                return { {this, bucket}, found };
            }

            std::pair<iterator, bool> insert(KeyT&& key, ValueT&& value) {
                check_expand_need();
                const auto bucket = find_or_allocate(key);
                const auto found = NEXT_BUCKET(_pairs, bucket) == INACTIVE;
                if (found) {
                    NEW_KVALUE(std::move(key), std::move(value), bucket);
                }
                else {
                    _pairs[bucket].orderid += incid();
                    update_orderid(incid());
                }
                return { {this, bucket}, found };
            }

            inline std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT>& p) {
                return insert(p.first, p.second);
            }

            inline std::pair<iterator, bool> insert(std::pair<KeyT, ValueT>&& p) {
                return insert(std::move(p.first), std::move(p.second));
            }

#if 0
            template <typename Iter>
            void insert(Iter begin, Iter end)
            {
                reserve(std::distance(begin, end) + _num_filled);
                for (; begin != end; ++begin) {
                    emplace(*begin);
                }
            }

            void insert(std::initializer_list<value_type> ilist)
            {
                reserve(ilist.size() + _num_filled);
                for (auto begin = ilist.begin(); begin != end; ++begin) {
                    emplace(*begin);
                }
            }

            template <typename Iter>
            void insert2(Iter begin, Iter end)
            {
                Iter citbeg = begin;
                Iter citend = begin;
                reserve(std::distance(begin, end) + _num_filled);
                for (; begin != end; ++begin) {
                    if (try_insert_mainbucket(begin->first, begin->second) == INACTIVE) {
                        std::swap(*begin, *citend++);
                    }
                }

                for (; citbeg != citend; ++citbeg)
                    insert(*citbeg);
            }

            uint32_t try_insert_mainbucket(const KeyT& key, const ValueT& value)
            {
                const auto bucket = hash_bucket(key);
                auto next_bucket = NEXT_BUCKET(_pairs, bucket);
                if (next_bucket != INACTIVE)
                    return INACTIVE;

                NEW_KVALUE(key, value, bucket);
                return bucket;
            }
#endif

            template <typename Iter>
            void insert_unique(Iter begin, Iter end) {
                reserve(std::distance(begin, end) + _num_filled);
                for (; begin != end; ++begin) {
                    insert_unique(*begin);
                }
            }

            /// Same as above, but contains(key) MUST be false
            uint32_t insert_unique(const KeyT& key, const ValueT& value) {
                check_expand_need();
                auto bucket = find_unique_bucket(key);
                NEW_KVALUE(key, value, bucket);
                return bucket;
            }

            uint32_t insert_unique(KeyT&& key, ValueT&& value) {
                check_expand_need();
                auto bucket = find_unique_bucket(key);
                NEW_KVALUE(std::move(key), std::move(value), bucket);
                return bucket;
            }

            uint32_t insert_unique(entry<KeyT, ValueT>&& pair) {
                auto bucket = find_unique_bucket(pair.first);
                NEW_KVALUE(std::move(pair.first), std::move(pair.second), bucket);
                return bucket;
            }

            inline uint32_t insert_unique(std::pair<KeyT, ValueT>&& p) {
                return insert_unique(std::move(p.first), std::move(p.second));
            }

            inline uint32_t insert_unique(std::pair<KeyT, ValueT>& p) {
                return insert_unique(p.first, p.second);
            }

            template <class... Args>
            inline std::pair<iterator, bool> emplace(Args&&... args) {
                return insert(std::forward<Args>(args)...);
            }

            // no any optimize for position
            template <class... Args>
            iterator emplace_hint(const_iterator position, Args&&... args) {
                return insert(std::forward<Args>(args)...).first;
            }

            template <class... Args>
            std::pair<iterator, bool> try_emplace(key_type&& k, Args&&... args) {
                return insert(k, std::forward<Args>(args)...).first;
            }

            template <class... Args>
            inline std::pair<iterator, bool> emplace_unique(Args&&... args) {
                return insert_unique(std::forward<Args>(args)...);
            }

            std::pair<iterator, bool> insert_or_assign(const KeyT& key, ValueT&& value) {
                return insert(key, std::move(value));
            }

            std::pair<iterator, bool> insert_or_assign(KeyT&& key, ValueT&& value) {
                return insert(std::move(key), std::move(value));
            }

            /// Like std::map<KeyT,ValueT>::operator[].
            ValueT& operator[](const KeyT& key) {
                check_expand_need();
                auto bucket = find_or_allocate(key);
                /* Check if inserting a new value rather than overwriting an old entry */
                if (NEXT_BUCKET(_pairs, bucket) == INACTIVE) {
                    NEW_KVALUE(key, std::move(ValueT()), bucket);
                }
                else {
                    _pairs[bucket].orderid += incid();
                    update_orderid(incid());
                }
                return EMH_VAL(_pairs, bucket);
            }

            ValueT& operator[](KeyT&& key) {
                check_expand_need();
                auto bucket = find_or_allocate(key);
                /* Check if inserting a new value rather than overwriting an old entry */
                if (NEXT_BUCKET(_pairs, bucket) == INACTIVE) {
                    NEW_KVALUE(std::move(key), std::move(ValueT()), bucket);
                }
                else {
                    _pairs[bucket].orderid += incid();
                    update_orderid(incid());
                }
                return EMH_VAL(_pairs, bucket);
            }

            // -------------------------------------------------------
            /// Erase an element from the hash table.
            /// return 0 if element was not found
            size_type erase(const KeyT& key) {
                const auto bucket = erase_key(key);
                if (bucket == INACTIVE)
                    return 0;

                clear_bucket(bucket);
                return 1;
            }

            // iterator erase(const_iterator begin_it, const_iterator end_it)
            iterator erase(const_iterator cit) {
                iterator it(this, cit._bucket);

                const auto bucket = erase_bucket(it._bucket);
                clear_bucket(bucket);
                // erase from main bucket, return main bucket as next
                return (bucket == it._bucket) ? ++it : it;
            }

            void _erase(const_iterator it) {
                const auto bucket = erase_bucket(it._bucket);
                clear_bucket(bucket);
            }

            constexpr bool is_notrivially() noexcept {
#if __cplusplus >= 201402L || _MSC_VER > 1600 || __clang__
                return !(std::is_trivially_destructible<KeyT>::value &&
                    std::is_trivially_destructible<ValueT>::value);
#else
                return !(std::is_pod<KeyT>::value && std::is_pod<ValueT>::value);
#endif
            }

            void clearkv() {
                for (uint32_t bucket = 0; _num_filled > 0; ++bucket) {
                    if (NEXT_BUCKET(_pairs, bucket) != INACTIVE)
                        clear_bucket(bucket);
                }
            }

            /// Remove all elements, keeping full capacity.
            void clear() {
                if (is_notrivially() || sizeof(PairT) > 32 ||
                    _num_filled < _num_buckets / 4)
                    clearkv();
                else
                    memset(_pairs, INACTIVE, sizeof(_pairs[0]) * _num_buckets);

                _num_filled = 0;
                _sum_orderid = 0;
            }

            inline void update_orderid(int32_t incr) { _sum_orderid += incr; }

            void shrink_to_fit() { rehash(_num_filled); }

            /// Make room for this many elements
            bool reserve(uint64_t num_elems) {
                const auto required_buckets = (uint32_t)(num_elems * _loadlf >> 27);
                if (EMHASH_LIKELY(required_buckets < _num_buckets))
                    return false;

                if (_num_filled >= _max_buckets * 2) {
                    auto ret = remove_half();
#if EMHASH_SAVE_MEMORY
                    if (_num_filled < _num_buckets / 4)
                        rehash(_num_filled);
#endif
                    return ret;
                }

                rehash(required_buckets + 2);
                return true;
            }

            bool remove_half() {
                auto ts = clock();
                uint32_t erase_ids = _num_filled;
                //
                //        for (uint32_t src_bucket = 0; src_bucket < _num_buckets;
                //        src_bucket++)
                //            sumid += _pairs[src_bucket].orderid;
                //        assert(_sum_orderid == sumid);

                auto sumid = _sum_orderid;
                auto medium_id = uint32_t(sumid / _num_filled);
                const auto tnows = entry<KeyT, ValueT>::nextid();

                uint32_t max_id = 1;
                for (uint32_t src_bucket = 0; src_bucket < _num_buckets; src_bucket++) {
                    auto& orderid = _pairs[src_bucket].orderid;
                    if (orderid > medium_id) {
                        if (orderid > max_id)
                            max_id = orderid;
#if EMHASH_TIME_DELAY
                        if (tnows + EMHASH_TIME_DELAY < orderid) {
                            update_orderid(tnows + EMHASH_TIME_DELAY - orderid);
                            orderid = tnows + EMHASH_TIME_DELAY;
                            continue;
                        }
                        else if (tnows < orderid + EMHASH_TIME_DELAY)
                            continue;
#else
                        continue;
#endif
                    }
                    else if (orderid == 0)
                        continue;

                    const auto bucket = erase_bucket(src_bucket);
                    clear_bucket(bucket);
                    if (bucket != src_bucket)
                        src_bucket--;
                }

#if EMHASH_REHASH_LOG || EMHASH_USE_LOG
                char buff[256] = { 0 };
                snprintf(buff, sizeof(buff),
                    "    _num_filled medium_id.pack_size.erase_ids load_factor|%u %u "
                    "%zu %u %.3f|, time_use = %d ms",
                    _num_filled, medium_id, sizeof(_pairs[0]), erase_ids - _num_filled,
                    load_factor(), (int)(clock() - ts));
#if EMHASH_USE_LOG
                static uint32_t iremoves = 0;
                FDLOG("lru_size") << __FUNCTION__ << " removes = " << iremoves++ << "|"
                    << buff << endl;
#else
                puts(buff);
#endif
#endif

                return erase_ids > 0;
            }

            void rehash(uint32_t required_buckets) {
                if (required_buckets < _num_filled)
                    return;

                uint32_t num_buckets = _num_filled > 65536 ? (1u << 16) : 8u;
                while (num_buckets < required_buckets) {
                    num_buckets *= 2;
                }

                auto new_pairs = (PairT*)malloc((2 + num_buckets) * sizeof(PairT));
                auto old_num_filled = _num_filled;
                auto old_pairs = _pairs;

                _num_filled = 0;
                _num_buckets = num_buckets;
                _mask = num_buckets - 1;

                for (uint32_t bucket = 0; bucket < num_buckets; bucket++) {
                    NEXT_BUCKET(new_pairs, bucket) = INACTIVE;
                    new_pairs[bucket].orderid = 0;
                }
                memset(new_pairs + num_buckets, 0, sizeof(PairT) * 2);

                _pairs = new_pairs;
                for (uint32_t src_bucket = 0; _num_filled < old_num_filled; src_bucket++) {
                    if (NEXT_BUCKET(old_pairs, src_bucket) == INACTIVE)
                        continue;

                    const auto& key = EMH_KEY(old_pairs, src_bucket);
                    const auto bucket = find_unique_bucket(key);
                    new (_pairs + bucket) PairT(std::move(old_pairs[src_bucket]));
                    _num_filled++;
                    NEXT_BUCKET(_pairs, bucket) = bucket;
                    if (is_notrivially())
                        old_pairs[src_bucket].~PairT();
                }

#if EMHASH_REHASH_LOG
                if (_num_filled > EMHASH_REHASH_LOG) {
                    char buff[255] = { 0 };
                    snprintf(
                        buff, sizeof(buff),
                        "    _num_filled/load_factor/K.V/pack/nextid = %u/%.3f/%s.%s/%zd|%u",
                        _num_filled, load_factor(), typeid(KeyT).name(),
                        typeid(ValueT).name(), sizeof(_pairs[0]),
                        entry<KeyT, ValueT>::nextid());
#if EMHASH_USE_LOG
                    static uint32_t ihashs = 0;
                    FDLOG() << "hash_nums = " << ihashs++ << "|" << __FUNCTION__ << "|"
                        << buff << endl;
#else
                    puts(buff);
#endif
                }
#endif

                free(old_pairs);
                assert(old_num_filled == _num_filled);
            }

        private:
            // Can we fit another element?
            inline bool check_expand_need() { return reserve(_num_filled); }

            void clear_bucket(uint32_t bucket) {
                update_orderid(0 - _pairs[bucket].orderid);
                if (is_notrivially())
                    _pairs[bucket].~PairT();

                NEXT_BUCKET(_pairs, bucket) = INACTIVE;
                _pairs[bucket].orderid = 0;
                _num_filled--;
            }

            uint32_t erase_key(const KeyT& key) {
                const auto bucket = hash_bucket(key);
                auto next_bucket = NEXT_BUCKET(_pairs, bucket);
                if (next_bucket == INACTIVE)
                    return INACTIVE;

                const auto eqkey = _eq(key, EMH_KEY(_pairs, bucket));
                if (next_bucket == bucket) {
                    return eqkey ? bucket : INACTIVE;
                }
                else if (eqkey) {
                    const auto nbucket = NEXT_BUCKET(_pairs, next_bucket);
                    if (is_notrivially())
                        EMH_PKV(_pairs, bucket).swap(EMH_PKV(_pairs, next_bucket));
                    else
                        EMH_PKV(_pairs, bucket) = EMH_PKV(_pairs, next_bucket);

                    NEXT_BUCKET(_pairs, bucket) = (nbucket == next_bucket) ? bucket : nbucket;
                    return next_bucket;
                } /* else if (EMHASH_UNLIKELY(bucket != hash_bucket(EMH_KEY(_pairs,
                     bucket)))) return INACTIVE;
                 */

                auto prev_bucket = bucket;
                while (true) {
                    const auto nbucket = NEXT_BUCKET(_pairs, next_bucket);
                    if (_eq(key, EMH_KEY(_pairs, next_bucket))) {
                        NEXT_BUCKET(_pairs, prev_bucket) =
                            (nbucket == next_bucket) ? prev_bucket : nbucket;
                        return next_bucket;
                    }

                    if (nbucket == next_bucket)
                        break;
                    prev_bucket = next_bucket;
                    next_bucket = nbucket;
                }

                return INACTIVE;
            }

            uint32_t erase_bucket(const uint32_t bucket) {
                const auto next_bucket = NEXT_BUCKET(_pairs, bucket);
                const auto main_bucket = hash_bucket(EMH_KEY(_pairs, bucket));
                if (bucket == main_bucket) {
                    if (bucket == next_bucket)
                        return bucket;

                    const auto nbucket = NEXT_BUCKET(_pairs, next_bucket);
                    if (is_notrivially())
                        EMH_PKV(_pairs, bucket).swap(EMH_PKV(_pairs, next_bucket));
                    else {
                        const auto orderid = _pairs[bucket].orderid;
                        EMH_PKV(_pairs, bucket) = EMH_PKV(_pairs, next_bucket);
                        _pairs[next_bucket].orderid = orderid;
                    }
                    NEXT_BUCKET(_pairs, bucket) = (nbucket == next_bucket) ? bucket : nbucket;
                    return next_bucket;
                }

                const auto prev_bucket = find_prev_bucket(main_bucket, bucket);
                NEXT_BUCKET(_pairs, prev_bucket) =
                    (bucket == next_bucket) ? prev_bucket : next_bucket;
                return bucket;
            }

            // Find the bucket with this key, or return bucket size
            uint32_t find_filled_bucket(const KeyT& key) {
                const auto bucket = hash_bucket(key);
                auto next_bucket = NEXT_BUCKET(_pairs, bucket);

                if (next_bucket == INACTIVE)
                    return _num_buckets;
                else if (_eq(key, EMH_KEY(_pairs, bucket))) {
                    _pairs[bucket].orderid += incid();
                    update_orderid(incid());
                    return bucket;
                }
                else if (next_bucket == bucket)
                    return _num_buckets;

#if EMHASH_LRU_GET
                auto prev_bucket = bucket;
#endif
                while (true) {
                    if (_eq(key, EMH_KEY(_pairs, next_bucket))) {
                        _pairs[next_bucket].orderid += incid();
                        update_orderid(incid());
#if EMHASH_LRU_GET
                        if (_pairs[next_bucket].orderid > _pairs[prev_bucket].orderid) {
                            EMH_PKV(_pairs, next_bucket).swap(EMH_PKV(_pairs, prev_bucket));
                            return prev_bucket;
                        }
                        else
#endif
                            return next_bucket;
                    }

#if EMHASH_LRU_GET
                    prev_bucket = next_bucket;
#endif
                    const auto nbucket = NEXT_BUCKET(_pairs, next_bucket);
                    if (nbucket == next_bucket)
                        break;
                    next_bucket = nbucket;
                }

                return _num_buckets;
            }

            // main --> prev --> bucekt -->next --> new
            uint32_t kickout_bucket(const uint32_t main_bucket, const uint32_t bucket) {
                const auto next_bucket = NEXT_BUCKET(_pairs, bucket);
                const auto new_bucket = find_empty_bucket(next_bucket);
                const auto prev_bucket = find_prev_bucket(main_bucket, bucket);
                NEXT_BUCKET(_pairs, prev_bucket) = new_bucket;
                new (_pairs + new_bucket) PairT(std::move(_pairs[bucket]));
                _num_filled++;
                if (next_bucket == bucket)
                    NEXT_BUCKET(_pairs, new_bucket) = new_bucket;

                update_orderid(_pairs[bucket].orderid);  // erase will clear orderid
                clear_bucket(bucket);
                return bucket;
            }

            /*
            ** inserts a new key into a hash table; first, check whether key's main
            ** bucket/position is free. If not, check whether colliding node/bucket is in
            *its main
            ** position or not: if it is not, move colliding bucket to an empty place and
            ** put new key in its main position; otherwise (colliding bucket is in its
            *main
            ** position), new key goes to an empty position.
            */
            uint32_t find_or_allocate(const KeyT& key) {
                const auto bucket = hash_bucket(key);
                const auto& bucket_key = EMH_KEY(_pairs, bucket);
                auto next_bucket = NEXT_BUCKET(_pairs, bucket);
                if (next_bucket == INACTIVE || _eq(key, bucket_key))
                    return bucket;

                // check current bucket_key is in main bucket or not
                const auto main_bucket = hash_bucket(bucket_key);
                if (main_bucket != bucket)
                    return kickout_bucket(main_bucket, bucket);
                else if (next_bucket == bucket)
                    return NEXT_BUCKET(_pairs, next_bucket) = find_empty_bucket(next_bucket);

#if EMHASH_LRU_SET
                auto prev_bucket = bucket;
#endif
                // find next linked bucket and check key
                while (true) {
                    if (_eq(key, EMH_KEY(_pairs, next_bucket))) {
#if EMHASH_LRU_SET
                        EMH_PKV(_pairs, next_bucket).swap(EMH_PKV(_pairs, prev_bucket));
                        return prev_bucket;
#else
                        return next_bucket;
#endif
                    }

#if EMHASH_LRU_SET
                    prev_bucket = next_bucket;
#endif

                    const auto nbucket = NEXT_BUCKET(_pairs, next_bucket);
                    if (nbucket == next_bucket)
                        break;
                    next_bucket = nbucket;
                }

                // find a new empty and link it to tail
                const auto new_bucket = find_empty_bucket(next_bucket);
                return NEXT_BUCKET(_pairs, next_bucket) = new_bucket;
            }

            // key is not in this map. Find a place to put it.
            uint32_t find_empty_bucket(const uint32_t bucket_from) {
                auto bucket = bucket_from + 1;
                if (NEXT_BUCKET(_pairs, bucket) == INACTIVE ||
                    NEXT_BUCKET(_pairs, ++bucket) == INACTIVE)
                    return bucket;

                // for (uint32_t last = 2, slot = 3; ; slot += last, last = slot - last) {
                for (uint32_t last = 1, slot = 4;; slot += ++last) {
                    auto bucket1 = (bucket_from + slot) & _mask;
                    if (NEXT_BUCKET(_pairs, bucket1) == INACTIVE ||
                        NEXT_BUCKET(_pairs, ++bucket1) == INACTIVE)
                        return bucket1;

                    if (last > 4) {
                        auto& next = NEXT_BUCKET(_pairs, _num_buckets);
                        if (INACTIVE == NEXT_BUCKET(_pairs, next++) ||
                            INACTIVE == NEXT_BUCKET(_pairs, next++))
                            return next - 1;

                        auto medium = (_num_buckets / 2 + next) & _mask;
                        if (INACTIVE == NEXT_BUCKET(_pairs, medium) ||
                            INACTIVE == NEXT_BUCKET(_pairs, ++medium))
                            return medium;

                        next &= _mask;
                    }
                }
            }

            uint32_t find_last_bucket(uint32_t main_bucket) const {
                auto next_bucket = NEXT_BUCKET(_pairs, main_bucket);
                if (next_bucket == main_bucket)
                    return main_bucket;

                while (true) {
                    const auto nbucket = NEXT_BUCKET(_pairs, next_bucket);
                    if (nbucket == next_bucket)
                        return next_bucket;
                    next_bucket = nbucket;
                }
            }

            uint32_t find_prev_bucket(uint32_t main_bucket, const uint32_t bucket) const {
                auto next_bucket = NEXT_BUCKET(_pairs, main_bucket);
                if (next_bucket == bucket)
                    return main_bucket;

                while (true) {
                    const auto nbucket = NEXT_BUCKET(_pairs, next_bucket);
                    if (nbucket == bucket)
                        return next_bucket;
                    next_bucket = nbucket;
                }
            }

            uint32_t find_unique_bucket(const KeyT& key) {
                const auto bucket = hash_bucket(key);
                auto next_bucket = NEXT_BUCKET(_pairs, bucket);
                if (next_bucket == INACTIVE)
                    return bucket;

                // check current bucket_key is in main bucket or not
                const auto main_bucket = hash_bucket(EMH_KEY(_pairs, bucket));
                if (main_bucket != bucket)
                    return kickout_bucket(main_bucket, bucket);
                else if (next_bucket != bucket)
                    next_bucket = find_last_bucket(next_bucket);

                // find a new empty and link it to tail
                return NEXT_BUCKET(_pairs, next_bucket) = find_empty_bucket(next_bucket);
            }

            static constexpr uint64_t KC = UINT64_C(11400714819323198485);
            static inline uint64_t hash64(uint64_t key) {
#if __SIZEOF_INT128__
                __uint128_t r = key;
                r *= KC;
                return (uint64_t)(r >> 64) + (uint64_t)r;
#elif _WIN64
                uint64_t high;
                return _umul128(key, KC, &high) + high;
#elif 1
                uint64_t r = key * UINT64_C(0xca4bcaa75ec3f625);
                return (r >> 32) + r;
#elif 1
                // MurmurHash3Mixer
                uint64_t h = key;
                h ^= h >> 33;
                h *= 0xff51afd7ed558ccd;
                h ^= h >> 33;
                h *= 0xc4ceb9fe1a85ec53;
                h ^= h >> 33;
                return h;
#elif 1
                uint64_t x = key;
                x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
                x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
                x = x ^ (x >> 31);
                return x;
#endif
            }

            // the first cache line packed
            template <typename UType,
                typename std::enable_if<std::is_integral<UType>::value,
                uint32_t>::type = 0>
            inline uint32_t hash_bucket(const UType key) const {
#if 1
                return (uint32_t)hash64(key) & _mask;
#elif EMHASH_SAFE_HASH
                if (_hash_inter > 0)
                    return (uint32_t)hash64(key) & _mask;

                return _hasher(key);
#elif EMHASH_IDENTITY_HASH
                return (key + (key >> (sizeof(UType) * 4))) & _mask;
#elif WYHASH_LITTLE_ENDIAN0
                return wyhash64(key, _num_buckets) & _mask;
#else
                return _hasher(key) & _mask;
#endif
            }

            template <typename UType,
                typename std::enable_if<std::is_same<UType, std::string>::value,
                uint32_t>::type = 0>
            inline uint32_t hash_bucket(const UType& key) const {
#ifdef WYHASH_LITTLE_ENDIAN
                return wyhash(key.c_str(), key.size(), key.size()) & _mask;
#elif EMHASH_BKR_HASH
                uint32_t hash = 0;
                for (int i = 0, j = 1; i < key.size(); i += j++)
                    hash = key[i] + hash * 131;
                return hash & _mask;
#else
                return _hasher(key) & _mask;
#endif
            }

            template <
                typename UType,
                typename std::enable_if<!std::is_integral<UType>::value &&
                !std::is_same<UType, std::string>::value,
                uint32_t>::type = 0>
            inline uint32_t hash_bucket(const UType& key) const {
                return _hasher(key) & _mask;
            }

        private:
            PairT* _pairs;
            HashT _hasher;
            EqT _eq;
            uint32_t _loadlf;
            uint32_t _num_buckets;
            uint32_t _max_buckets;
            uint32_t _mask;

            uint32_t _num_filled;
            uint64_t _sum_orderid;
    };
}  // namespace emlru_size
#if __cplusplus > 199711
// template <class Key, class Val> using emihash = emhash1::lru_cache<Key, Val,
// std::hash<Key>>;
#endif
